package com.masterlu.leetcode.daily.heap.simple;

import java.util.*;

/**
 * 最后一块石头的重量
 * https://leetcode-cn.com/problems/last-stone-weight/
 *
 * @date created in 2021/5/24 14:06
 */
public class S1046LastStoneWeight {

    public int lastStoneWeight(int[] stones) {

        List<Integer> list = new ArrayList<>();
        for (int stone : stones) {
            list.add(stone);
        }

        list.sort((o1, o2) -> o1 - o2);

        while (list.size() > 1) {
            int last = list.get(list.size() - 1);
            list.remove(list.size() - 1);
            int last2 = list.get(list.size() - 1);
            list.remove(list.size() - 1);

            if ((last - last2) != 0) {
                list.add(Math.abs(last - last2));
            }
            list.sort((o1, o2) -> o1 - o2);
        }


        if (list.isEmpty()) {
            list.add(0);
        }

        return list.get(0);
    }

    public int lastStoneWeight2(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (int stone : stones) {
            queue.offer(stone);
        }

        while (queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            if (a > b) {
                queue.offer(a - b);
            }
        }

        return queue.isEmpty() ? 0 : queue.poll();
    }
}
